package com.classicInterview;

/**
 * 倒水问题，有arr的一个容器，求解可以倒多少水，
 *
 * @Author: huangzhigao
 * @Date: 2022/2/12 14:23
 */
public class Water {
    /**
     * 思路i位置每次可以倒的水的数量为左边最大值与右边最大的值中最小的一个 - i位置的高度
     *
     * @param arr
     * @return
     */
    public int getWater(int[] arr) {
        int left = 1;
        int right = arr.length - 2;
        //左边容器最大的高度
        int leftMax = arr[0];
        //右边容器最大的高度
        int rightMax = arr[arr.length - 1];
        int res = 0;

        while (left <= right) {
            if (leftMax <= rightMax) {
                //左小，则左边left位置可以增加leftMax-arr[left]的水量
                res += Math.max(0, leftMax - arr[left]);
                leftMax = Math.max(leftMax, arr[left++]);
            } else {
                res += Math.max(0, rightMax - arr[right]);
                rightMax = Math.max(rightMax, arr[right--]);
            }
        }


        return res;

    }


    /**
     * 给你一个二维数组，每一个值代表这一个地形的高度，求整块地形能装下多少水
     *
     * 解题思路
     * 将二维数组的四周 每个元素生成一个对象（num,row,col）加入小根堆，以num值作比较，维护一个进入过小根堆的bool二维数组
     * 维护一个全局最大值max，每次从小根堆弹出堆顶，并更新max值，并将它上下左右未进过小根堆的元素加入小根堆（在加入时，计算水量，max-元素值）
     *
     */
}
